//You are given two non-empty linked lists representing two non-negative 
//integers. The most significant digit comes first and each of their nodes contains a 
//single digit. Add the two numbers and return the sum as a linked list. 
//
// You may assume the two numbers do not contain any leading zero, except the 
//number 0 itself. 
//
// 
// Example 1: 
// 
// 
//Input: l1 = [7,2,4,3], l2 = [5,6,4]
//Output: [7,8,0,7]
// 
//
// Example 2: 
//
// 
//Input: l1 = [2,4,3], l2 = [5,6,4]
//Output: [8,0,7]
// 
//
// Example 3: 
//
// 
//Input: l1 = [0], l2 = [0]
//Output: [0]
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in each linked list is in the range [1, 100]. 
// 0 <= Node.val <= 9 
// It is guaranteed that the list represents a number that does not have 
//leading zeros. 
// 
//
// 
// Follow up: Could you solve it without reversing the input lists? 
//
// Related Topics 栈 链表 数学 👍 599 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

class P445AddTwoNumbersIi{
    //2023-05-13 10:51:16
    //Add Two Numbers II
    //编号：[445]
    
    public static void main(String[] args) {

        ListNode l1 = new ListNode(7);
        ListNode l2 = new ListNode(2);
        System.out.println(addTwoNumbers(l1, l2));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        while (l1 != null) {
            list1.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            list2.add(l2.val);
            l2 = l2.next;
        }
        int size1 = list1.size() - 1;
        int size2 = list2.size() - 1;
        int add = 0;
        List<Integer> newList = new ArrayList<>();
        while (size1 >= 0 || size2 >= 0) {
            Integer i1 = 0;
            Integer i2 = 0;
            if (size1 >= 0 && size2 >= 0) {
                i1 = list1.get(size1);
                i2 = list2.get(size2);
            } else if (size1 >= 0) {
                i1 = list1.get(size1);
            } else if (size2 >= 0) {
                i2 = list2.get(size2);
            }
            int i = i1 + i2 + add;
            if (i >= 10) {
                add = 1;
                i = i - 10;
            } else {
                add = 0;
            }
            size1--;
            size2--;
            newList.add(0, i);
        }
        if (add != 0) {
            newList.add(0, add);
        }
        ListNode root = new ListNode();
        ListNode tempNode = root;
        for (Integer nodeValue : newList) {
            tempNode.next = new ListNode(nodeValue);
            tempNode = tempNode.next;
        }
        return root.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}